package october;

import java.util.Arrays;
import java.util.Random;

/*
You have been given a series of 'n' numbers and the series is in a random order. Write a program to find the median of the series with minimum complexity.
*/
public class MedianFinder {
    public static void main(String[] args) {
        int n = 9;
        int max = 7;
        int[] a = new int[n];
        Random random = new Random();
        for (int i = 0; i < n; i++) a[i] = random.nextInt(max);
        final int median = selectKth(a, a.length / 2);
        Arrays.sort(a);
        System.out.println("The median of " + Arrays.toString(a) + " :  " + median);
    }

    public static int selectKth(int[] arr, int k) {
        if (arr == null || arr.length <= k) throw new IllegalArgumentException();
        int from = 0, to = arr.length - 1;

        while (from < to) {// if from == to we reached the kth element
            int left = from, right = to;
            int pivot = arr[(left + right) / 2];

            // stop if the reader and writer meets
            while (left < right) {

                if (arr[left] >= pivot) { // put the large values at the end
                    swap(arr,left,right);
                    right--;
                } else { // the value is smaller than the pivot, skip
                    left++;
                }
            }
            // if we stepped up (left++) we need to step one down
            if (arr[left] > pivot)
                left--;

            // the left pointer is on the end of the first k elements
            if (k <= left) {
                to = left;
            } else {
                from = left + 1;
            }
        }

        return arr[k];
    }

    private static void swap(int[] a, int l, int r) {
        int temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
}
